Algorithm and Complexity (2017) Class Website

 

Algorithm and Complexity (2017)

基本信息 (General Information)

Level: Undergraduate
Time & Place: 4:00pm-5:40pm (Dong Zhong Yuan 305)
Instructor:
  • Name: Xiaofeng Gao
  • Email: gao-xf(at)cs.sjtu.edu.cn
  • Office: Telecom Building 3-328
  • Phone: 021-34207407
Teaching Assistant:
  • Name: Haotian Wang
  • Email: ltwbwht@qq.com
  • Office: SEIEE 3-309 (EAST)
  • Phone: 34207407
  • Office Hour:
  • Name: Lei Jiang
  • Email: john_ray@qq.com
  • Office: SEIEE 3-309 (EAST)
  • Phone: 34207407
  • Office Hour:
Back to Top 　　　　

课堂时间 (Course Schedule)

Back to Top

计划日程 (Syllabus)

Week

Date

Lecture Topic

Event

TA

1

Feb.20

Syllabus, Preliminary, Introduction to Algorithm

Schedule, Grading Policy, Preliminary, Basic Introduction, etc.

1

Feb.23

Algorithm Design and Analysis

Sorting Algorithm, Time Complexity, Space Complexity, etc.

Lab-01

2

Feb.27

Divide-and-Conquer (1)

Mergesort, Selection, Master’s Theorem etc.

2

Mar.02

Divide-and-Conquer (2)

Sorting Network

Lab-02

3

Mar.06

Greedy Approach (1)

Interval Scheduling, Interval Partitioning, Minimum Lateness, etc

3

Mar.09

Greedy Approach (2)

Matroid, Greedy-Max Algorithm

Lab-03

4

Mar.13

Greedy Approach (3)

Matroid, Task Scheduling Problem

4

Mar.16

Dynamic Programming (1)

Weighted Interval Scheduling, Segmented Least Squares, Knapsack, etc

Lab-04

5

Mar.20

Dynamic Programming (2)

RNA Secondary Structure, Sequence Alignment, etc.

Lab-05

5

Mar.23

Course Review

Exercises, Midterm Review, Applications, etc.

6

Mar.27

Midterm Exam

Midterm

6

Mar.30

Amortized Analysis (1)

Aggregate Analysis, Accounting Method

6

Apr.01

Amortized Analysis (2)

Potential Method, Dynamic Table, etc.

Lab-06

7

Apr.03

National Holiday

7

Apr.06

Graph Algorithms (1)

Searching and Exploration, etc

8

Apr.10

Graph Algorithms (2)

Single Source Shortest Paths, (Greedy & DP) etc

8

Apr.13

Graph Algorithms (3)

All-Pairs Shortest Paths, etc

Lab-07

9

Apr.17

Graph Algorithms (4)

Maximum Flow, Minimum Cut, etc

9

Apr.20

Turing Machine

Turing Machine, etc.

Lab-08

10

Apr.24

Computability

Church's Thesis, etc.

10

Apr.27

NP-Completeness (1)

NP class, Polynomial time, etc.

Lab-09

11

May 01

National Holiday

11

May 04

NP-Completeness (2)

Reducibility, Proofs, etc.

Lab-10

12

May 08

NP-Completeness (3)

Reduction, Applications, etc.

12

Review. Final Exam

Final

Back to Top

作业与课后阅读 (Assignments and Readings)

Lecture 1: Preliminary - Basic Mathematical Objects

  • Reading Materials
  • Lab 0: Self-Introduction
    • Please complete your Self-Introduction (Due: 02/23/2017)  
    • Click the "Log-In" button at the top-right of this webpage then update your information. 

Lecture 2: Algorithm Analysis

Lecture 3: Divide and Conquer

Lecture 4: Sorting Network

Lecture 5: Greedy Strategy

Lecture 6: Matroid

Lecture 7: Dynamic Programming

Lecture 8: Dynamic Programming (2)

Lecture 9: Amortized Analysis

Lecture 10: Graph Algorithms

Lecture 11: Graph Exploration

Lecture 12: Shortest Path

Lecture 13: Max Flow and Minimum Spanning Tree

  • Max Flow and Min Cut
  • Minimum Spanning Tree
    • Slide15-MST:   Slide15-MST.pdf
    • Slide Print Version:   15-MST.pdf
    • Reference: Chapter 4.5, 4.7 in "Algorithm Design" by J. Kleinberg, and E. Tardos, Pearson-Addison Wesley, 2005. (Check Reference05-GreedyAlgorithm.pdf) 

Lecture 14: Turing Machine

Lecture 15: NP and Reduction

Lecture 16: NP and Reduction (2)

Back to Top

提交引导 (Submission Guidelines)

  • 请登录右上角的JAccount进行作业提交，登录后可以下载课件、提交作业。
    Please log in by JAccountat the top right corner to download course materials and submit your homework.
  • 作业只能提交一个文档，如果有多个文档请放在一个文件夹里，将其压缩成.rar或.zip文件。作业可以多次提交，每次上传版本会覆盖原来版本。可通过点击右上方“Check Hw.”一栏查看作业提交、成绩与反馈情况（建议下载检查上传版本)。
    You can only submit ONE document for each homework. If there are multiple documents, please put them inside a folder, and compress it in the form of .rar or .zip You can submit homework multiple times, while the original submitted version will be covered by the latest submitted one. You can click on “Check Hw.”at the top right corner to check the homework submission, grade, and feedback.(Suggestion: You can download your submitted homework to check it.)
  • 若已登录的情况下提示权限不足，请刷新或者注销后重新登录，若仍权限不足，请及时与助教联系。如出现无法提交、不懂操作、系统Bug等情况请与助教及时联系。
    If it shows that you do not have access after you log in, please refresh the webpage or re-log in again. If it still does not work, please contact teaching assistants in time. If you have other problems, e.g., you cannot or don’t know how to submit your homework, or find Bugs please contact your teaching assistants in time.
Back to Top

学生名册与课堂记录 (Roster and Event)


Roster

Class Attendance Pictures

Class Project Pictures

Back to Top

引用材料 (Reference)

  • Algorithm
    • T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, The MIT Press, 2009
    • M. H. Alsuwaiyel, Algorithm Design Technique and Analysis, World Scientific, 1999.
    • Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, Algorithm, McGraw-Hill, 2007.
    • J. Kleinberg, and E. Tardos, Algorithm Design, Pearson-Addison Wesley, 2005.
    • Alfred V. Aho, John E Hopcroft, Jeffery D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
    • Udi Manber, Introduction to Algorithms: A Creative Approach, Addison-Wesley, 1989.
    • Henming Zou, The Way of Algorithms, China Machine Press, 2010.
  • Computational Complexity:
    • Christos Papadimitriou, Computational Complexity, Addison Wesley, 1994.
    • Theory of Computational Complexity, by Ding-Zhu Du, and Ker-I Ko, published by John Wiley & Sons, Inc., 2000.
    • John Martin, Introduction to Languages and the Theory of Computation, McGraw-Hill, 2002.
    • Computational Complexity: A Modern Approach, by Sanjeev Arora and Boaz Barak, Cambridge University Press, 2006.
  • Approximation:
    • Vijay V. Vazirani, Approximation Algorithms, Springer-Verlag, 2001.
    • D.P. Williamson and D.B. Shmoys, The Design of Approximation Algorithms, 2011.
    • D.Z Du, K-I. Ko, and X.D. Hu, Design and Analysis of Approximation Algorithms, 2012.
  • Acknowledgement:
    • Special thanks is given to Prof. Kevin Wayne, Prof. Charles E. Leiserson, Prof. Salah E. Elmaghraby, Prof. Neeraj Mittal, Prof. Ding-Zhu Du, Prof. Yuxi Fu, Prof. Yijia Chen, Prof. Pinyan Lu, Dr. Xiaojuan Cai for sharing their teaching materials.
Back to Top